package com.leetcode.www;
import java.util.*;
/**
 * Creared with IntelliJ IDEA.
 * Description:全排列   给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案
 * User:yxd
 * Date:2022-04-14
 * Time:14:11
 */
public class DFS46 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        boolean[] bool = new boolean[nums.length];//标记矩阵
        DFS(ret,list,0,nums,bool);
        return ret;
    }
    public void DFS(List<List<Integer>> ret,List<Integer> list,int index,int[] nums,boolean[] bool){
        if(list.size() == nums.length){
            ret.add(new ArrayList<>(list));
            return;
        }

        for(int i = 0;i < nums.length;i ++){
            if(!bool[i]){
                bool[i] = true;
                list.add(nums[i]);
                DFS(ret,list,i,nums,bool);
                bool[i] = false;
                list.remove(list.size() - 1);
            }

        }
    }

}
